It is well known that data can be encrypted by utilising a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted by the public key may only be decrypted by the private key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipients private key.
The most well known and accepted public key cryptosystems are those based on discrete logarithms in finite groups and integer factorization. In particular, the Diffie-Hellman key exchange and the El Gamal protocol in Z.sup.*.sub.p, p a prime and the RSA system for modulus n=p.multidot.q where p and q are primes have been implemented worldwide. One disadvantage of these systems is that p and n must be relatively large (at least 512 bits) to attain an adequate level of security.
To implement the public key schemes it is necessary to transfer the public key of a recipient to the sender or for the sender to store the keys of all possible recipients. For this reason researchers have looked for public key schemes which reduce the size of the public key. An attractive and promising system is the Diffie-Hellman and El Gamal protocols defined in the group associated with the points on an elliptic curve over a finite field. It appears that a 155-bit elliptic curve scheme gives comparable security to a 1024-bit RSA modulus. Nevertheless, RSA remains a very viable and practical encryption and signing process.
The implementation of RSA system requires a modulus n to be generated from two primes, p,q. The primes p,q, are also used to select a pair of integers, d,e, that are related such that the product e.d.ident.1 (mod (p-1)(q-1) and that the GCD (greatest common denominator) of e, p-1 and q-1=1.
The integers e together with the modulus n is used as the public key and the integer d with the modulus n is used as the private key. To encrypt a message the sender uses the public key e,n of the recipient and exponentiates the message M to the integer `e` mod n to generate ciphertext C. The recipient receives the ciphertext C and uses the private key d,n to retrieve the message M by exponentiating C to power d mod n. Therefore the communication between the sender and recipient requires the sender to have access to the public key of the recipient. Typically the public key will be retrieved from the recipient at the start of transmission or it may be stored by the sender. The public key must also be associated with other information such as the recipients identity and be transmitted in a conventional frame format. Accordingly, it is desirable for the data that has to be transmitted to be as short as possible.
On the other hand, the security of the RSA system is determined by the difficulty in factoring the modulus n and this requires p and q to be as large as possible, typically at least 256 bits but preferably 512. n itself will therefore also be large, either 512 or 1024 bits.
It is an object of the present invention to provide a method for reducing the storage and transmission requirement of RSA public module without compromising security.